package com.demo.data.struct2.排序.快速排序2;

import com.demo.data.struct2.排序.Util;

// 单边循环快排
public class QuickSort {

	public static void main(String[] args) {
		int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
		quick(a, 0, a.length - 1);
		Util.display(a);
	}
	
	public static void quick(int[] a, int l, int h) {
		if(l >= h) {
			return;
		}
		int p = sort(a, l, h); // p: 索引值
		quick(a, l, p-1); // 左边分区的范围确定
		quick(a, p+1, h); // 右边分区的范围确定
	}

	private static int sort(int[] a, int l, int h) {
		int pv = a[h]; // 基准点元素
		int i = l;
		for(int j=l; j<h; j++) {
			if(a[j] < pv) {
				if(i != j) {
					Util.swap(a, i, j);
				}
				i++;
			}
		}
		if(i != h) {
			Util.swap(a, h, i);
		}
		return i;
	}
	
}
